package ufmg.maze.ga;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import ufmg.maze.Maze;

public class GeneticAlgorithm {

	private Maze maze;

	public static int MUTACAO_PROB = 10;
	public static int CROSS_PROB;
	
	public static int N = 1200; 
	public static int RODADA = 20;
	
	private static final Random rand = new Random();
	
	private Individuo melhor = null;

	public GeneticAlgorithm(Maze maze) {
		this.maze = maze;
	}

	public List<Individuo> gerarPopulacao(int tamanho) {
		System.out.println("Gerando popula��o inicial com "+tamanho+" indiv�duos...");
		List<Individuo> individuos = new ArrayList<Individuo>();
		for (int i = 0; i < tamanho; i++) {
			individuos.add(Individuo.criarIndividuo(maze.getTamanho(), maze));
		}
		System.out.println("Gera��o conclu�da!");
		return individuos;
	}
	
	private Individuo torneio(List<Individuo> populacao, Maze maze, int k)
	{
		Individuo melhorTorneio = null;
		for(int i=0; i<k; i++)
		{
			do{
				int ind = rand.nextInt(populacao.size());
				if(melhorTorneio==null)
					melhorTorneio = populacao.get(ind);
				if(melhorTorneio.fitness(maze)>populacao.get(ind).fitness(maze))
					melhorTorneio = populacao.get(ind);
			}while(melhorTorneio.getIndiceFinal()==0);
		}
		return melhorTorneio;
	}
	
	public List<Individuo> selecao(int n, List<Individuo> populacao)
	{
		List<Individuo> selecionados = new ArrayList<Individuo>();
		
		for(int i=0; i<n; i++)
		{
			selecionados.add(populacao.get(i));
		}
		
		return selecionados;
	}
	
	public void avaliacaoFitness(List<Individuo> populacao)
	{
		double min = maze.getLimiteX()*maze.getLimiteY()*100;
		for(Individuo individuo : populacao){
			double fit = individuo.fitness(this.maze);
			if(fit < min){
				melhor = individuo;
				min = fit;
			}
		}
	}

	public void init(int tamanhoPopulacaoInicial) {
		List<Individuo> populacao = gerarPopulacao(tamanhoPopulacaoInicial);
		avaliacaoFitness(populacao);
		int rodada = 0;
		System.out.println("Evoluindo a popula��o...");
		while (true) {
			List<Individuo> childs = new ArrayList<Individuo>();
			Individuo i1 = null;
			Individuo i2 = null;
			
			while(childs.size() < tamanhoPopulacaoInicial){
				do{
					i1 = torneio(populacao,maze,10);
					i2 = torneio(populacao,maze,10);
				}while(i1.equals(i2));
				
				childs.addAll(i1.cross(i2));
				i1.mutate(); i2.mutate();
			}
			
			//List<Individuo> selecionados = selecao(populacao.size()/10, populacao);
			//childs.addAll(selecionados);
		
			populacao = childs;
			
			// Elistismo
			populacao.add(melhor);
			
			//ordenaPorFitness(populacao);
			
			++rodada;

			if(rodada == RODADA){
				break;
			}
		}
		
		System.out.println("Evolu��o conclu�da! Inspecionando melhor indiv�duo...");
		avaliacaoFitness(populacao);
		
		System.out.println();
		if(melhor != null){
			System.out.println("Melhor solu��o encontrada: "+melhor.fitness(maze));
			melhor.print(maze);
		}else{
			System.out.println("N�o foi encontrada uma solu��o vi�vel!");
		}
	}

	private void ordenaPorFitness(List<Individuo> populacao) {
		Collections.sort(populacao, new Comparator<Individuo>() {

			@Override
			public int compare(Individuo o1, Individuo o2) {
				
				return (int)(o1.fitness(maze) - o2.fitness(maze));
			}
		});
	}

}

